I. Field of the Invention
The invention generally relates to computer graphics and in particular to techniques for rendering 3-D surfaces.
II. Description of the Related Art
A long-standing problem in computer graphics is the rendering of surface images based upon actual 3-D objects, particularly moving objects. In particular, significant problems arise in the generation of an internal computer representation of the surface of a 3-D object. Unlike 2-D images, which can merely be scanned into a computer then stored therein using a simple pixel representation, 3-D objects cannot be easily scanned into a computer nor conveniently stored therein. The problem of generating an internal surface representation of an actual 3-D object is made significantly worse if the object is in motion or is otherwise changing shape.
One of technique that has shown some promise for rendering the surfaces of actual 3-D objects involves the extraction and subsequent volume projection of 2-D silhouettes of the object. Conceptually, the silhouette projection technique operates as follows. A 3-D object is imaged from various imaging points. A binary silhouette or matte of the object is extracted from each image. Each silhouette is then projected or extruded in three dimensions yielding a corresponding Boolean volume cylinder having a perimeter cross-section matching the perimeter of the corresponding silhouette. The cylinders are then combined in accordance with the relative locations of the imaging points yielding a set of intersecting cylinders. The intersection portions of the cylinders collectively define a 3-D surface, which approximates the 3-D object. The 3-D surface is, itself, then approximated using polygons. The polygons thus provide a 3-D surface representation of the surface of the object. The polygonal representation of the surface of the 3-D object then can be internally manipulated using the computer to, for example, generate displays of the object from any desired direction or perhaps to morph the object into other shapes. The number of polygons employed to approximate the intersecting portions of the cylinders can be increased, as desired, to approximate the intersecting portions with arbitrary accuracy. However, only an increase in the number of initial silhouettes in combination with an increase in the number of polygons can yield a more faithful representation of the original object.
To incorporate perspective into the 3-D surface representation of the object, the distance from each imaging point to the object is taken into account during the projection process. To this end, each silhouette is projected into a volume cone, rather than a cylinder, with the cone having a perimeter cross-section matching the perimeter of the corresponding silhouette. Again, a final 3-D surface representation is generated by combining the volume cones, determining the intersection of the surfaces of the cones, and generating a polyhedral representation of that surface. The aforementioned technique is described in From images to models (and beyond): a personal retrospective, by Richard Szeliske, Vision Interface 97, May 21, 1997.
A significant advantage of the silhouette projection technique is that it requires as input only simple 2-D images of the object, which may be generated by a simple video camera or similar imaging device. Unfortunately, in use, the silhouette projection technique does not yield a very faithful representation of the original object unless a very large number of initial images are taken from all sides of the object. To provide the large number of initial images, the object is typically placed on a rotating turntable adjacent to the video camera. The video camera generates an entire sequence of image frames of the object as the object slowly rotates on the turntable relative to the video camera. Each image frame is processed to extract a silhouette of the object. Accordingly, a large number of silhouettes are generated requiring a considerable amount of the processing time to generate the corresponding volume projections, to combine the projections, and to generate the polyhedral representation of intersecting surface portions of the combined projections. Thus, although the fidelity with which the object is represented improves by using a large number of input images, the required processing time is often prohibitive. Moreover, real time imaging of the object is typically completely precluded. In this regard, real-time imaging would likely require dozens or perhaps hundreds of video cameras simultaneously imaging the object from all sides to generate, at each point in time, the large number of input images required to faithfully represent the object. Additionally, vast computing power would be required to process the dozens or hundreds of images, at each point in time, to extract the corresponding silhouettes, to generate the volume projections, to combine the volume projections, and to generate a polyhedral representation of the intersection of the combined volume projections.
One of the reasons that the silhouette projection technique requires a large number of input images to generate a faithful representation of an object is that the intersection of combined volume projections of silhouettes of an object simply does not provide a very good approximation of the object. In this regard, consider the application of the silhouette projection technique to a simple sphere using three initial images, from the front, top and side of the sphere, respectively. As can be appreciated, the silhouettes extracted from the initial images are merely circles. When the circles are projected into volume projections, simple cones are generated. The intersection of three cones, however, does not produce an intersecting surface that closely corresponds to a sphere. Rather, the intersection of three cones produces a somewhat angular geometric object. Only when a large number of cones are intersected along a large number of radial directions will the resulting intersecting surface closely approximate the sphere.
Thus, even in the case of a simple sphere, which should be easy to represent because of its three dimensional symmetry, the silhouette projection technique does not yield a faithful representation unless a large number of silhouettes are processed. As can be appreciated, more complicated objects will likely require far more silhouettes than the sphere to provide even a reasonable representation of the object.
Accordingly, it would be desirable to provide an improved silhouette projection technique that requires relatively few input images yet yields a faithful representation of a 3-D object. As can be appreciated, such a technique would reduce the processing time required to generate the final surface representation of the object, thereby rendering the technique much more practical and economical. Moreover, if sufficiently few input images are required, real time rendering of a moving or otherwise changing 3-D object becomes feasible. It is to these ends, that various aspects of the present invention are directed.